#include<vector>
#include<climits>
using namespace std;
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int m=coins.size(),n=amount;
        vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
        dp[0][0]=0;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                dp[i][j]=dp[i-1][j];
                if(j-coins[i-1]>=0&&dp[i][j-coins[i-1]]!=INT_MAX)
                    dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
            }
        }
        return dp[m][n]==INT_MAX?-1:dp[m][n];
    }
};
//空间优化
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int m=coins.size(),n=amount;
        vector<int>dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                dp[j]=dp[j];
                if(j-coins[i-1]>=0&&dp[j-coins[i-1]]!=INT_MAX)
                    dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
            }
        }
        return dp[n]==INT_MAX?-1:dp[n];
    }
};